package airthmetic.exercise.cacheobsolescence;

import java.util.HashMap;

public class _146_LRU缓存 {

    HashMap<Integer, Node> hashTable;
    Node head;
    Node tail;
    int capacity;
    int size;

    public _146_LRU缓存(int capacity) {
        this.capacity = capacity;
        hashTable = new HashMap<Integer, Node>(capacity);
        head = new Node();
        tail = new Node();
        this.size = 0;

        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        // 获取不存在返回-1
        Node node = hashTable.get(key);
        if (node == null) {
            return -1;
        }

        // 走到这里说明存在 1.将元素删除 将节点添加到头哨兵后面 2.返回元素
        moveToHead(node);
        return node.value;
    }

    public void moveToHead(Node node) {
        removeNode(node);
        insertToHead(node);
    }

    public void insertToHead(Node node){
        Node firstNode = head.next;
        head.next = node;
        node.prev = head;
        node.next = firstNode;
        firstNode.prev = node;
    }

    public void removeNode(Node node) {
        Node prev = node.prev;
        Node next = node.next;
        prev.next = next;
        next.prev = prev;
        node.prev = null;
        node.next = null;
    }


    public void put(int key, int value) {
        Node node = hashTable.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
            return;
        }
        // 走到这里说明元素为空 创建元素，放入hashTable 放入链表头部  size++ 判断是否超出长度 删除末尾元素 size--
        node = new Node(key, value);
        hashTable.put(key, node);
        insertToHead(node);
        this.size++;
        if (size > capacity) {
            Node removeNode = removeTail();
            hashTable.remove(removeNode.key);
            this.size--;
        }

    }

    public Node removeTail() {
        Node last = tail.prev;
        Node prev = last.prev;
        prev.next = tail;
        tail.prev = prev;
        last.prev = null;
        last.next = null;

        return last;
    }

    class Node {
        int key;
        int value;
        Node prev;
        Node next;

        public Node() {

        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        _146_LRU缓存 lru缓存 = new _146_LRU缓存(2);

        lru缓存.put(1, 1);
        lru缓存.put(2, 2);

        System.out.println(lru缓存.get(1));
        lru缓存.put(3, 3);
        System.out.println(lru缓存.get(2));

        lru缓存.put(4, 4);
        System.out.println(lru缓存.get(1));
        System.out.println(lru缓存.get(3));
        System.out.println(lru缓存.get(4));


    }
}
